Cell switching is a method of transmitting digital information wherein the information is broken into equal sized units called "cells." The cells of information are usually grouped into larger units called "frames."
The individual cells of information are transmitted from a source node to a destination node through a "connection." A connection consists of a pathway through a digital network. A digital network is constructed of digital switches coupled together by digital communication lines.
Each cell originates at a source node and is transmitted across the communications lines. The communication lines carry the cells of information between the digital switches along the connection pathway. The digital switches route the cells from incoming communication lines to outgoing communication lines and finally to a destination node coupled to a digital switch.
Each digital switch can be connected to several communication lines. Furthermore, each communication line can carry several different connections simultaneously. Every connection must be served by the digital switch. Serving a connection entails removing an incoming cell from an input queue associated with the connection and sending the cell out on a communication line or to a destination node coupled to the digital switch. A service algorithm is employed to select a connection for service. To fully utilize the bandwidth of a communication line, a cell must be selected for service during each service time. The service time refers to the amount of time it takes to transmit a single cell onto the communication line.
The objective of the service algorithm is to ensure that each connection receives the appropriate amount of service. This can be achieved by controlling the rate at which each connection is served. Current methods of rate control use linear searches to find a connection that is qualified to be served. The time available to complete the search through the list of connections is equal to the service time of a connection. With modern high speed links, this service time is much smaller than service time using older technology. Furthermore, modern high speed links are expected to carry more connections than older technology. Having more connections reduces the amount of time available to scan the list of connections. The combined effect of more connections and less time to service each connection is making it increasingly difficult for technology to keep up using standard linear approaches of rate control.